package algorithmic_data_structure.并查集;

import org.junit.Test;

import java.util.Stack;

//也可以使用dfs
public class P547_省份数量 {
    @Test
    public void test(){
        System.out.println(findCircleNum(new int[][]{
                {1, 1, 0},
                {1, 1, 0},
                {0, 0, 1}
        }));
        System.out.println(findCircleNum(new int[][]{
                {1, 1, 1},
                {1, 1, 1},
                {1, 1, 1}
        }));
        System.out.println(findCircleNum(new int[][]{
                {1, 0, 1, 1},
                {0, 1, 0, 0},
                {1, 0, 1, 0},
                {1, 0, 0, 1},
        }));
    }
    public int findCircleNum(int[][] isConnected) {
        int cityNums = isConnected.length;
        int[] citySize = new int[cityNums];
        int[] father = new int[cityNums];
        for (int i = 0; i < cityNums; i++) {
            father[i] = i;
            citySize[i] = 1;
        }
        for (int i = 0; i < cityNums; i++) {
            for (int j = i+1; j < cityNums; j++) {
                if (isConnected[i][j] == 1){
                    union(i,j,father,citySize);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < cityNums; i++) {
            if (citySize[i] != 0){
                res++;
            }
        }
        return res;
    }

    private void union(int i, int j, int[] father, int[] citySize) {
        int iFa = findFather(i,father,citySize);
        int jFa = findFather(j,father,citySize);
        //小的认大的做爹
        if (iFa == jFa){
            //在同一个集合中，不做操作
        }
        else if (iFa > jFa){
            callFather(iFa,jFa,father,citySize);
        }else{
            callFather(jFa,iFa,father,citySize);
        }
    }
    private void callFather(int iFa, int jFa, int[] father, int[] citySize) {
        father[iFa] = jFa;
        citySize[jFa] += citySize[iFa];
        citySize[iFa] = 0;
    }
    // 从i开始一直往上，往上到不能再往上，代表节点，返回
    // 这个过程要做路径压缩
    Stack<Integer> stack = new Stack<>();
    private int findFather(int x, int[] father, int[] citySize) {
        while (father[x] != x){//把到父亲节点的沿途节点都记录下来，并指向父节点
            stack.push(x);
            x = father[x];
        }
        int t ;
        while (!stack.isEmpty()){
            t = stack.pop();
            father[t] = x;
            citySize[t] = 0;
            citySize[x]++;
        }
        return x;
    }
}
